#include <cmath>
#include <iostream>
#include <queue>

using namespace std;

class Main
{
  public:
    struct TreeNode
    {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(nullptr), right(nullptr)
        {
        }
    };

    bool isCompleteTree(TreeNode *root)
    {
        if (!root)
            return true;

        queue<TreeNode *> q;
        q.push(root);
        bool isEnd = false; // 标记是否已遇到第一个空节点

        while (!q.empty())
        {
            TreeNode *node = q.front();
            q.pop();

            // 检查左空右有的情况
            if (!node->left && node->right)
            {
                return false;
            }

            // 处理左子节点
            if (node->left)
            {
                if (isEnd)
                    return false; // 空节点后出现非空节点
                q.push(node->left);
            }

            else
            {
                isEnd = true; // 左子节点为空，标记进入空节点阶段
            }

            // 处理右子节点
            if (node->right)
            {
                if (isEnd)
                    return false; // 空节点后出现非空节点
                q.push(node->right);
            }
            else
            {
                isEnd = true; // 右子节点为空，标记进入空节点阶段
            }
        }
        return true;
    }
};

class Solution
{
  public:
    // struct TreeNode
    // {
    //     int val;
    //     TreeNode *left;
    //     TreeNode *right;
    //     TreeNode(int x) : val(x), left(nullptr), right(nullptr)
    //     {
    //     }
    // };
    bool isCompleteTree(TreeNode *root)
    {
        // write code here
        queue<TreeNode *> q;
        if (root == nullptr)
        {
            return false;
        }
        q.push(root);
        bool flag = false;
        while (!q.empty())
        {
            TreeNode *node = q.front();
            q.pop();
            if (!node->left && node->right)
                return false;

            if (node->left)
            {
                if (flag)
                    return false;//前一个是空，后一个不是，不符合完全二叉树特性
                q.push(node->left);
            }
            else
            {
                flag = true;//此节点为空，标记它
            }
            if (node->right)
            {
                if (flag)
                    return false;
                q.push(node->right);
            }
            else
            {
                flag = true;
            }
        }
        return true;
    }
};

int main()
{
    // 示例用法：
    // Main::TreeNode* root = new Main::TreeNode(1);
    // root->left = new Main::TreeNode(2);
    // root->right = new Main::TreeNode(3);
    // root->left->left = new Main::TreeNode(4);
    // Main main;
    // cout << main.isCompleteTree(root) << endl;  // 应输出1（true）
    return 0;
}